/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef __STD_VECTOR_H_VERSION_KL__
#define __STD_VECTOR_H_VERSION_KL__
#include "memory.h"

KL_BEGIN
// CLASS vector {
template<typename Type, class Allocate = allocator<Type>>
class vector
{
	// TYPE {
public:
	KL_TYPE_DEFINE(Type);
	STD_ITERATOR_DEFINE(pointer);
	typedef typename Allocate::template rebind<value_type>::other allocator_type;
protected:
	typedef _memory_helper_<value_type> _helper;
	typedef size_type _index_type;
	// TYPE }
protected: 
	// DATA {
	iterator _head;
	size_type _size;
	size_type _capacity;
	allocator_type _alloc;
	// DATA }
public:
	// CONSTRUCT {
	vector() : _head(0), _size(0), _capacity(0)
	{
	}
	explicit vector(size_type num)
		: _head(0), _size(0), _capacity(0)
	{
		this->_insert(_size, num);
	}
	vector(size_type num, value_type const &value)
		: _head(0), _size(0), _capacity(0)
	{
		this->_insert(_size, num, value);
	}
	vector(vector const &o)
		: _head(0), _size(0), _capacity(0)
	{
		this->_insert_i(_size, o._size, o._head);
	}
	template<class InIter>
	vector(InIter first, InIter last) 
		: _head(0), _size(0), _capacity(0)
	{
		size_type num = KL::distance(first, last);
		this->_insert_i(_size, num, first);
	}
	~vector()
	{
		_clear();
		_deallocate();
		_head = 0;
		_capacity = 0;
	}
	// CONSTRUCT }
	// OTHER {
	void swap(vector &o)
	{
		if(&o == this) return;
		_swap_(_size, o._size);
		_swap_(_head, o._head);
		_swap_(_capacity, o._capacity);
	}
	void reserve(size_type capacity) 
	{
		if(_capacity < capacity)
			this->_reserve(_fix(capacity));
	}
	void resize(size_type size, value_type const &value)
	{
		if(size > _size)
		{
			this->_insert(_size, size - _size, value);
		}
		else if(size < _size)
		{
			this->_erase(size, _size);
		}
	}
	void resize(size_type size)
	{
		if(size > _size)
		{
			this->_insert(_size, size - _size);
		}
		else if(size < _size)
		{
			this->_erase(size, _size);
		}
	}
	void clear()
	{
		_clear();
	}
	// OTHER }
	// ASSIGN {
	vector &operator =(vector const &o)
	{
		if(&o == this) return *this;
		this->_clear();
		this->_insert_i(_size/* 0 */, o._size, o._head);
		return *this;
	}
	void assign(size_type num, value_type const value)  
	{
		this->_clear();
		this->_insert(_size, num, value);
	}
	template<class InIter>
	void assign(InIter first, InIter last)  
	{
		size_type num = KL::distance(first, last);
		this->_clear();
		this->_insert_i(_size, num, first);
	}
	// ASSIGN }
	// ERASE & INSERT {
	iterator erase(const_iterator pos) 
	{
		_index_type i = pos - _head;
		ASSERT_REPAIR(i < _size, return end());
		this->_erase(i);
		return _head + i;
	}
#ifdef _USE_KL_EXTRA
	iterator erase(const_iterator pos, size_type num)
	{		
		_index_type i = pos - _head, j = i + num;
		ASSERT_REPAIR(i <= j && j <= _size, return end());
		this->_erase(i, j);
		return _head + i;
	}
#endif // _USE_KL_EXTRA
	iterator erase(const_iterator first, const_iterator last) 
	{
		_index_type i = first - _head, j = last - _head;
		ASSERT_REPAIR(i <= j && j <= _size, return end());
		this->_erase(i, j);
		return _head + i;
	}
	iterator insert(const_iterator pos, value_type const value) 
	{
		_index_type i = pos - _head;
		ASSERT_REPAIR(i <= _size, i = _size);
		this->_insert(i, value);
		return _head + i;
	}
	iterator insert(const_iterator pos, size_type num, value_type const value) 
	{
		_index_type i = pos - _head;
		ASSERT_REPAIR(i <= _size, i = _size);
		this->_insert(i, num, value);
		return _head + i;
	}
#ifdef _USE_KL_EXTRA
	iterator insert(const_iterator pos, size_type num)
	{
		_index_type i = pos - _head;
		ASSERT_REPAIR(i <= _size, i = _size);
		this->_insert(i, num);
		return _head + i;
	}
#endif // _USE_KL_EXTRA
	template<typename InIter>
	iterator insert(const_iterator pos, InIter first, InIter last) 
	{
		_index_type i = pos - _head;
		ASSERT_REPAIR(i <= _size, i = _size);
		size_type num = KL::distance(first, last);
		this->_insert_i(i, num, first);
		return _head + i;
	}
	// ERASE & INSERT }
	// PUSH & POP {
	void push_back(value_type const &value) 
	{
		this->_insert(_size, value);
	}
	void pop_back()  
	{
		ASSERT_REPAIR(_size, return);
		_erase(_size - 1);
	}
	// PUSH & POP }
	// ITERATOR {
	iterator begin()
	{
		return _head;
	}
	iterator end()
	{
		return _head + _size;
	}
	const_iterator begin() const
	{
		return _head;
	}
	const_iterator end() const
	{
		return _head + _size;
	}
	reverse_iterator rbegin()
	{
		return reverse_iterator(_head + _size - 1);
	}
	reverse_iterator rend()
	{
		return reverse_iterator(_head - 1);
	}
	const_reverse_iterator rbegin() const
	{
		return const_reverse_iterator(_head + _size + 1);
	}
	const_reverse_iterator rend() const
	{
		return const_reverse_iterator(_head - 1);
	}
	// ITERATOR }
	// VISIT {
	value_type & operator[](size_type pos)  
	{
		ASSERT(pos < _size);
		return _head[pos];
	}
	value_type & at(size_type pos)  
	{
		ASSERT(pos < _size);
		return _head[pos];
	}
	const value_type & operator[](size_type pos) const  
	{
		ASSERT(pos < _size);
		return _head[pos];
	}
	const value_type & at(size_type pos) const  
	{
		ASSERT(pos < _size);
		return _head[pos];
	}
	value_type & back()  
	{
		ASSERT(_size != 0);
		return _head[_size - 1];
	}
	value_type & front()  
	{
		ASSERT(_size != 0);
		return _head[0];
	}
	const value_type & back() const  
	{
		ASSERT(_size != 0);
		return _head[_size - 1];
	}
	const value_type & front() const  
	{
		ASSERT(_size != 0);
		return _head[0];
	}
	bool empty() const
	{
		return _size == 0;
	}
	size_type size() const
	{
		return _size;
	}
	size_type capacity() const
	{
		return _capacity;
	}
	allocator_type &getallocator_type() const
	{
		return _alloc;
	}
	size_type max_size() const
	{
		return allocator_type::max_size();
	}
	// VISIT }
protected:
	// OPERATE {
	void _move(_index_type from, _index_type to, size_type num)
	{
		if(from == to) return;
		if(from < to) 
		{
			_helper::raw_move_backward_n(_head + from, num, _head + to);
		}
		else
		{
			_helper::raw_move_forward_n(_head + from, num, _head + to);
		}
	}
	void _expand(_index_type pos, size_type num)
	{
		if(_size + num <= _capacity)
		{
			if(_size > pos) 
			{
				_move(pos, pos + num, _size - pos);
			}
		}
		else
		{
			size_type capacity = _fix(_size + num);
			iterator head = this->_allocate(capacity);
			if(pos) 
			{
				_helper::raw_copy_n(_head, pos, head);
			}
			if(pos < _size) 
			{
				_helper::raw_copy_n(_head + pos, _size - pos, head + pos + num);
			}
			if(_size) _helper::destroy_n(_head, _size);
			this->_deallocate();
			_head = head;
			_capacity = capacity;
		}
		_size += num;
	}
	void _erase(_index_type pos /* < _size */)
	{
		_helper::destroy(_head + pos);
		if(pos + 1 < _size) _move(pos + 1, pos, _size - pos - 1);
		--_size;
	}
	void _erase(_index_type from /* <= to */, _index_type to /* <= _size */)
	{
		_helper::destroy_n(_head + from, to - from);
		if(to < _size) _move(to, from, _size - to);
		_size -= to - from;
	}
	void _insert(_index_type to, const_reference value)
	{
		_expand(to, 1);
		_helper::raw_fill(_head + to, value);
	}
	void _insert(_index_type to, size_type num)
	{
		_expand(to, num);
		_helper::initialize_n(_head + to, num);
	}
	void _insert(_index_type to, size_type num, const_reference value)
	{
		_expand(to, num);
		_helper::raw_fill_n(_head + to, num, value);
	}
	template<typename InIter>
	void _insert_i(_index_type to, size_type num, InIter &first)
	{
		_expand(to, num);
		_helper::raw_copy_n(first, num, _head + to);
	}
	void _clear()
	{
		if(_size) 
		{
			_helper::destroy_n(_head, _size);
			_size = 0;
		}
	}
	void _reserve(size_type capacity)
	{
		iterator head = this->_allocate(capacity);
		if(_size)
		{
			_helper::raw_copy_n(_head, _size, head);
			_helper::destroy_n(_head, _size);
		}
		this->_deallocate();
		_capacity = capacity;
		_head = head;
	}
	// OPERATE }
	// ALLOCATE {
	size_type _fix(size_type size)
	{
		static const size_t _PRE = 3;
		return ((size >> _PRE) + (size >> (_PRE + 1)) + 1) << _PRE;
	}	
	void _deallocate()
	{
		allocator_type::deallocate(_head, _capacity);
	}
	iterator _allocate(size_type capacity)
	{
		return allocator_type::allocate(capacity);
	}
	// ALLOCATE }
};
// CLASS vector }
// FUNCTION swap (for vector) {
template<typename Type, typename Allocate>
inline void swap(vector<Type, Allocate> &left, vector<Type, Allocate> &right)
{
	left.swap(right);
}
// FUNCTION swap (for vector) }
KL_END

#endif // __STD_VECTOR_H_VERSION_KL__
